package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.*;


class CommonParentNode{

    private HashMap<TreeNode,HashMap<TreeNode,TreeNode>> map;

    public CommonParentNode(TreeNode root) {

        map = new HashMap<>();
        initMap(root);
        addNode(root);
    }

    public TreeNode findCommonParentNode(TreeNode t1, TreeNode t2) {

        if (t1 == t2) {
            return t1;
        }

        if (map.get(t1) != null && map.get(t1).get(t2) != null) {

            return map.get(t1).get(t2);
        }

        if (map.get(t2) != null && map.get(t2).get(t1) != null) {

            return map.get(t2).get(t1);
        }

        return null;
    }

    public HashMap<TreeNode, HashMap<TreeNode, TreeNode>> getMap() {
        return map;
    }

    private void initMap(TreeNode node) {

        if (node == null) {

            return;
        }

        map.put(node,new HashMap<>());

        initMap(node.left);
        initMap(node.right);
    }

    private void addNode(TreeNode node) {

        if (node == null) {
            return;
        }

        // node 与左右子树每一个节点的公共最近父类为node
        addLeftOrRightNode(node.left,node);
        addLeftOrRightNode(node.right,node);
        preLeft(node.left,node.right,node);
        addNode(node.left);
        addNode(node.right);
    }

    private void addLeftOrRightNode(TreeNode node,TreeNode head) {

        if (node == null) {
            return;
        }

        map.get(node).put(head,head);
        addLeftOrRightNode(node.left, head);
        addLeftOrRightNode(node.right, head);

    }

    private void addBetween(TreeNode node) {

        preLeft(node.left,node.right,node);
    }

    private void preLeft(TreeNode leftNode,TreeNode rightNode,TreeNode head) {

        if (leftNode == null) {

            return;
        }
        preRight(leftNode,rightNode,head);
        preLeft(leftNode.left,rightNode,head);
        preLeft(leftNode.right,rightNode,head);
    }

    private void preRight(TreeNode leftNode, TreeNode rightNode,TreeNode head) {

        if (rightNode == null) {
            return;
        }

        map.get(leftNode).put(rightNode,head);
        preRight(leftNode,rightNode.left,head);
        preRight(leftNode,rightNode.right,head);
    }
}

public class _18_查找两个节点的最近公共父节点_map_all {

    public static void main(String[] args) {

        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.right = new TreeNode(10);

        CommonParentNode commonParentNode = new CommonParentNode(t1);
        for (Map.Entry<TreeNode, HashMap<TreeNode, TreeNode>> entry : commonParentNode.getMap().entrySet()) {

            System.out.print(entry.getKey().val +" [  ");
            for (Map.Entry<TreeNode, TreeNode> nodeEntry : entry.getValue().entrySet()) {

                System.out.print(nodeEntry.getKey().val + ":" + nodeEntry.getValue().val + "  ");
            }
            System.out.println("]");
        }
        TreeNode parentNode = commonParentNode.findCommonParentNode(t1.left.left, t1.right);
        System.out.println(parentNode);

    }
}
